Detecting the origin of text segments efficiently.
In the origin detection problem an algorithm is given a set S of documents, ordered by creation time, and a query document D. It needs to output for every consecutive sequence of k alphanumeric terms in D the earliest document in S in which the sequence appeared (if such a document exists). Algorithms for the origin detection problem can, for example, be used to detect the“origin”of text segments in D and thus to detect novel content in D. They can also find the document from which the author of D has copied the most (or show that D is mostly original.) We propose novel algorithms for this problem and evaluate them together with a large number of previously published algorithms. Our results show that (1) detecting the origin of text segments efficiently can be done with very high accuracy even when the space used is less than 1 % of the size of the documents in S, (2) the precision degrades smoothly with the amount of available space, (3) various estimation techniques can be used to increase the performance of the algorithms.
Alignment of Minisatellite Maps Based on Run%2DLength Encoding Scheme.

Alignment of Minisatellite Maps A Minimum Spanning Tree%2Dbased Approach.
In addition to the well-known edit operations, the alignment of minisatellite maps includes duplication events. We model these duplications using a special kind of spanning trees and deduce an optimal duplication scenario by computing the respective minimum spanning tree. Based on best duplication scenarios for all substrings of the given sequences, we compute an optimal alignment of two minisatellite maps. Our algorithm improves upon the previously developed algorithms in the generality of the model, in alignment quality and in space-time efficiency. Using this algorithm, we derive evidence that there is a directional bias in the growth of minisatellites of the MSY1 dataset.
An Improved Algorithm for the Macro%2Devolutionary Phylogeny Problem.

Reconstructing Domain Compositions of Ancestral Multi%2Ddomain Proteins.

DNA Compression Challenge Revisited A Dynamic Programming Approach.

Energy landscape of k%2Dpoint mutants of an RNA molecule.
doi:10.1093/bioinformatics/bti669

An improved algorithm for generalized comparison of minisatellites.


On the Transformation Distance Problem.
A K − partition of a set S is a splitting of S into K non-overlapping classes that cover all elements of S. Numerous practical applications dealing with data partitioning or clustering require computing the distance between two partitions. Previous articles proved that one can compute it in polynomial time—minimum O(|S | + K 2) and maximum O(|S | + K 3)—using a reduction to the linear assignment problem. We propose several conditions for which the partition distance can be computed in O(|S|) time. In practical terms, this computation can be done in O(|S|) time for any two relatively resembling partitions (i.e. with distance less than |S| 5) except specially constructed cases. Finally, we prove that, even if there is a bounded number of classes for which the proposed conditions are not satisfied, one can still preserve the linear complexity by exploiting decomposition properties of the similarity matrix. Key words: partition distance, partition metric, similarity between partitions, clustering comparison, similarity measure 1
The Minisatellite Transformation Problem Revisited A Run Length Encoded Approach.

An Improved Algorithm for Generalized Comparison of Minisatellites.

An approximate matching algorithm for finding %28sub%2D%29optimal sequences in S%2Dattributed grammars.

